package leetcode;

import java.util.*;

/**
 * 完全平方数
 */
public class LeetCode279 {
    public int numSquares(int n) {
        int i = 1;
        List<Integer> nums = new ArrayList<>();
        while (i * i <= n) nums.add(i * i++);
        Queue<Integer> queue = new LinkedList<>();
        for (int j = nums.size() - 1; j >= 0; j--) queue.offer(n - nums.get(j));
        queue.offer(null);
        int depth = 1;
        while (!queue.isEmpty()) {
            Integer node = queue.poll();
            if (node == null) {
                depth++;
                if (queue.peek() != null) queue.offer(null);
            } else if (nums.contains(node)) {
                return depth + 1;
            } else if (node == 0) {
                return depth;
            } else {
                for (Integer num : nums) {
                    if (node > num) queue.offer(node - num);
                }
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        LeetCode279 leetCode279 = new LeetCode279();
        System.out.println(leetCode279.numSquares(25));
    }

}